前面介绍的各种存储器管理方式，要求将一个作业全部装入内存后方能运行。于是出现了两种情况：

解决方法：

特征：

程序运行的局部性原理 1968年，Denning.P提出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。

程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。

过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但研究表明，过程调用的深度在大多数情况下不超过5。

程序中存在许多循环结构，由少数指令构成，但会多次执行。

程序中对许多数据结构的处理，往往都局限于很小的范围内。

局部性的表现：

虚拟存储器的定义 基于局部性原理，应用程序在运行前，没有必要全部装入内存，仅将当前要运行的部分页面或段先装入内存即可运行，其余部分暂留在外存上。程序运行时，如果要访问的页(段)已调入内存，便可继续执行；如果尚未调入内存(称为缺页或缺段)，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，使程序继续执行。如果内存已满，无法再装入新的页(段)，还必须利用页(段)的置换功能，将内存中暂时不用的页(段)调至外存，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行。 虚拟存储器：是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却接近于外存。

特征：

多次性：一个作业被分成多次调入内存运行

对换性：允许在作业的运行过程中进行换进、换出。

虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

虚拟性以多次性和对换性为基础； 多次性和对换性又必须建立在离散分配的基础上

请求分页系统是建立在基本分页基础上的，增加了请求调页功能和页面置换功能。换入和换出的基本单位都是长度固定的页面，因而在实现上比请求分段系统简单。

请求分页系统中的页表项： (1) 状态位P ：指示该页是否已调入内存。 (2) 访问字段A ：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问。 (3) 修改位M ：表示该页在调入内存后是否被修改过。 (4) 外存地址：用于指出该页在外存上的地址。

为进程分配内存时，涉及三个问题：

最小物理块数的确定 最小物理块数，指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行. 进程应获得的最小物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。 对于某些简单机器，若是单地址指令且采用直接寻址方式，最小物理块数应为2；如果该机器允许间接寻址，则至少要求3个物理块。 对于某些功能较强的机器，指令长度可能是两个或两个以上字节，至少要为进程分配6个物理块。

物理块的分配策略 在请求分页系统中，可以采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可以采取两种策略，即全局置换和局部置换。于是可以组合出三种适合的策略。

固定分配局部置换 基于进程的类型，或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间不再改变。 采用该策略时，如果进程在运行中发现缺页，只能从该进程在内存中的n个页面中选出一页换出，然后再调入一页。 困难：应为每个进程分配多少个物理块难以确定。

可变分配全局置换 在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲的物理块队列。如果某进程发生缺页时，由系统从空闲的物理块队列中，取出一个物理块分配给该进程，并将欲调入的页装入其中。

固定分配局部置换

可变分配全局置换

可变分配局部置换

基于进程的类型，或根据程序员的要求，为每个进程分配一定数目的物理块，如果某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，不会影响其他进程执行。如果进程在运行中频繁发生缺页中断，则系统再为进程分配若干物理快；如果进程在运行中缺页率特别低，则适当减少分配给该进程的物理块。

设作业执行中访问页面的总次数为A，其中有F次访问的页面尚 未装入主存，故产生了F次缺页中断。现定义缺页中断率为： f=F/A

最佳置换算法是一种理想化的算法，具有最好的性能，但难于实现。先进先出置换算法最直观，但可能性能最差，故应用极少。

最佳置换算法是从“向后看”的观点出发的，即它是根据以后各页的使用情况；而LRU算法则是“向前看”的，即根据各页以前的使用情况来判断，而页面过去和未来的走向之间并无必然的联系。

寄存器 1）寄存器 为每个在内存中的页面配置一个移位寄存器，用来记录某进程在内存中各页的使用情况。移位寄存器表示为 R=Rn-1Rn-2Rn-3…R2R1R0 当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间将寄存器右移一位。如果把n位寄存器的数看作一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。

栈 利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。

又称最近未使用算法(NRU, Not Recently Used)，LRU和FIFO的折衷。 原理：每页有一个使用标志位(use bit)，若该页被访问则置user bit=1。 置换时采用一个指针，从当前指针位置开始按地址先后检查各页，寻找use bit=0的页面作为被置换页。 指针经过的user bit=1的页都修改user bit=0，最后指针停留在被置换页的下一个页。

请求分页式虚拟存储器系统在正常运行情况下，能有效地减少内存碎片，提高处理机的利用率和吞吐量。 但如果在系统中运行的进程太多，进程在运行中会频繁地发生缺页情况，这又会对系统的性能产生很大的影响。 多道程序度与“抖动” 随着进程数目的增加，处理机利用率趋于0时是系统中已发生了“抖动”。 产生“抖动”的原因是同时在系统中运行的进程太多，而分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁的出现缺页，必须请求系统将所缺之页调入内存。 工作集 是指在某段时间间隔 里，进程实际所要访问页面的集合。

在请求分段系统中，程序运行之前，只需先调入若干个分段(不必调入所有的分段)，便可启动运行。当所访问的段不在内存中时，可请求OS将所缺的段调入内存。